package _01_动态数组;

import java.util.Arrays;


/**
 * @Author: haogege
 * @Date: 2021/9/20
 */
public class _31_下一个排列 {

    public static void main(String[] args) {


        _31_下一个排列 v = new _31_下一个排列();

        int[] ins = {2, 2, 7, 5, 4, 3, 2, 2, 1};
        v.nextPermutation(ins);

        System.out.println(Arrays.toString(ins));
    }


    // 此题意思也就是找到下一个比他大的数字，但是这个比他大的数字是其中最小的
    public void nextPermutation(int[] nums) {
        int right = nums.length - 1;
        int left = 0;
        // 从后往前找到第一个顺序对
        for (int i = right; i > 0; i--) {
            if (nums[i - 1] < nums[i]) {
                left = i;
                break;
            }
        }

        if (left != 0) {
            int minMin = left - 1;
            int minMax = 0;
            // 找到逆序对
            // 找到第一个大于left的值
            for (int i = right; i >= left; i--) {
                if (nums[i] > nums[left - 1]) {
                    minMax = i;
                    break;
                }
            }
            // 交换
            int temp = nums[minMin];
            nums[minMin] = nums[minMax];
            nums[minMax] = temp;
        }
        reverse(nums, left, right);
    }

    public void reverse(int[] nums, int left, int right) {
        while (left < right) {
            int temp = nums[left];
            nums[left++] = nums[right];
            nums[right--] = temp;
        }
    }

}
